package org.aplombh.java.leetcode.dailyTopic;

import java.util.Arrays;

public class _764最大加号标志 {
    public static void main(String[] args) {
        System.out.println(new Solution764_1().orderOfLargestPlusSign(5, new int[][]{{4, 2}}));
    }
}

// 动态规划

class Solution764_1 {
    public int orderOfLargestPlusSign(int n, int[][] mines) {

        int[][] f = new int[n][n];

        for (int[] ints : f) {
            Arrays.fill(ints, n);
        }

        for (int[] mine : mines) {
            f[mine[0]][mine[1]] = 0;
        }

        int max = 0;

        for (int i = 0; i < n; i++) {

            int leftToRight = 0, rightToLeft = 0, upToDown = 0, downTOup = 0;

            for (int j = 0, k = n - 1; j < n; j++, k--) {

                leftToRight = f[i][j] > 0 ? leftToRight + 1 : 0;
                rightToLeft = f[i][k] > 0 ? rightToLeft + 1 : 0;
                upToDown = f[j][i] > 0 ? upToDown + 1 : 0;
                downTOup = f[k][i] > 0 ? downTOup + 1 : 0;

                f[i][j] = Math.min(f[i][j], leftToRight);
                f[i][k] = Math.min(f[i][k], rightToLeft);
                f[j][i] = Math.min(f[j][i], upToDown);
                f[k][i] = Math.min(f[k][i], downTOup);

            }
        }

        for (int[] ints : f) {
            for (int anInt : ints) {
                max = Math.max(max, anInt);
            }
        }

        return max;
    }
}